Sau khi bình định toàn xứ Austrasia, Charles hành quân tấn công quân đội Frisia của vua Radbod, đẩy lui họ và thậm chí buộc Radbod phải nhượng miền Tây Frisia (nay là Hà Lan). Dưới danh nghĩa vua Clotaire, ông cũng đánh bật người Saxon qua bên kia sông Weser, bảo đảm vùng biên giới.Năm 718, Chilperic đáp trả sự lớn mạnh của Charles bằng việc liên minh với Odo Vĩ đại (còn gọi là Eudes), vị công tước xứ Aquitaine vốn trung lập trong cuộc nội chiến năm 715, nhưng một lần nữa thất bại trước Charles ở Soissons. Cả Chilperic và Odo phải bỏ trốn tới vùng đất phía bắc sông Loire còn Ragenfrid tới xứ Angers. Clotaire IV mất sau đó ít lâu còn Odo thì đầu hàng Charles đề duy trì tước vị công tước.

Các cuộc chiến thời kỳ 718-731

Trong những năm 718-723, Charles củng cố quyền lực bằng các cuộc chinh phục Bayern và Allemannia. Với việc đánh bại những người Saxon ngoại đạo đã làm tăng ảnh hưởng của Charles đối với các vị giám mục và tu viện trưởng, bên cạnh việc hiến đất và tiền cho các quỹ của nhà thờ.

Sau khi đã đoàn kết được người Frank, Charles quyết định tấn công người Saxon, xua đuổi dân tộc này tới các vùng sông Weser, sông Lippe và sông Ruhr. Ông đánh bại quân đội Saxon ở rừng Teutoburg. Năm 719 Charles thu hồi lại miền Tây Frisia mà không gặp sự kháng cự đáng kể nào. Dân Frisia là những người ngoại đạo nhưng lãnh tụ của họ, Adgillis II theo đạo Cơ đốc và Charles đã cử Willibrord, giám mục xứ Utrecht, "tông đồ của người Frisia" đến cải đạo cho dân chúng, cũng như sau này ông đã ủng hộ mạnh mẽ cho W"infrid hay Thánh Boniface, "tông đồ của người German".

Khi Chilperic II chết một năm sau (720), Charles đặt đứa con còn nhỏ của Dagobert III, Theuderic IVlên ngôi vua Neustria. Theuderic, cũng như nhiều vị vua khác mà Charles bổ nhiệm, hoàn toàn là những kẻ bù nhìn. Năm đó, Charles lại cất quân đánh người Saxon. Ragenfrid nhân cơ hội rời bá quốc (county) Anjou, khởi xuống một cuộc nổi loạn của người Neustria, nhưng đã bị đánh bại dễ dàng vào năm 724. Charles vẫn cho Ragenfrid giữ lại lãnh địa Anjou, nhưng phải lần lượt gửi những người con trai làm con tin. Cuộc nội chiến người Frank đến đây hoàn toàn chấm dứt.

Tiếp đó Charles phải đối phó với các xu hướng tách ra độc lập của các bộ lạc German. Những năm 720-723 ông tiến đánh xứ Bavaria nơi các công tước dòng Agilolfing trở nên ngày càng tỏ ra tự chủ và đã bắt tay với người Lombard chống lại Charles. Charles buộc công tước Hugbert xứ Barvaria và miền Alemannia khuất phục chính quyền Frank. Một chiến dịch nữa ở Bavaria kéo dài trong những năm 725-728, ông đã trở về cùng với công chúa Swanachild, người có lẽ đã trở thành vợ lẽ của ông. Năm 730, Lantfrid, công tước xứ Alemannia lại nổi loạn và Charles phải đem quân dẹp. Lantfrid bị chết trong trận chiến, Charles quyết định không đặt người kế vị mà sáp nhập miền Bắc Đức vào lãnh thổ vương quốc Frank.

Trước trận Tours

Tuy nhiên, trong thời kỳ này, một mối đe dọa mới đến với nhà nước Frank của Charles, đó là đội quân Hồi giáo của đế quốc Ả Rập từ phương Nam.

Năm 721, tiểu vương (émir) Córdoba đã xây dựng một đội quân mạnh từ Maroc, Yemen, và Syria để xâm lược Aquitaine, công quốc lớn nằm ở phía Tây Nam của xứ Gaul, về danh nghĩa thuộc quyền của vương triều Frank nhưng thực tế hầu như độc lập từ khi triều đình Merovingian suy yếu. Quân đội Hồi giáo đã vây hãm Toulouse, thành phố quan trọng nhất của Aquitaine, và công tước Aquitaine, Odo Vĩ đại, buộc phải rời khỏi để tìm cứu viện.

Odo trở lại sau ba tháng khi thành phố gần như sắp đầu hàng và đánh bại quân Hồi giáo vào ngày 9 tháng 6 năm 721, nay được biết tới tên Trận Toulouse. Sự thất bại của người Ả Rập chủ yếu là kết quả của sự dàn mỏng lực lượng: họ đã trở nên quá tự tin khi Odo bỏ đi và rải quân đi cướp bóc xung quanh và khi Odo trở lại, họ bị bất ngờ và binh lính bỏ chạy vứt cả vũ khí và áo giáp. Tuy nhiên sức mạnh và ý chí xâm lược của người Ả Rập không bị tổn thất nhiều bởi trận này.

Nhiều sử gia cho rằng, mặc dù thường xuyên đánh nhau với người Saxon, phương Nam mới là mối quan tâm chính của Charles.[13][14] Trước tình hình ở bán đảo Iberia, Charles tin rằng ông cần thời gian để xây dưng một đội quân gần như thường trực được luyện tập thường xuyên làm nòng cốt cho quân đội Frank với số đông là lính nghĩa vụ được trưng tập khi có nhu cầu chiến tranh (ở châu Âu sơ kỳ trung đại, quân đội chỉ tập trung được khi ngũ cốc đã được gieo và trước vụ gặt). Muốn thế phải trả lương đủ cao cho binh lính, và Charles tìm cách lấy tiền từ ngân quỹ của Giáo hội mà trước kia ông từng hỗ trợ. Việc này diễn ra trong những năm 724-732 khiến cho quan hệ của ông với nhà thờ trở nên căng thẳng, có lúc dường như ông sẽ bị rút phép thông công.

Cần phải nói rằng, trong khi Charles đã chuẩn bị từ sớm thì đối thủ của ông lúc ấy còn chưa biết nhiều về sức mạnh của quân đội Frank. Sách "Biên niên sử Ả Rập", tư liệu lịch sử chủ yếu của thời bấy giờ, chỉ ghi nhận sự lo ngại của người Ả Rập về Charles Martel từ sau trận Tours.